{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Duplicate Node LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeDuplicateNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #移除重复节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。</p>\n",
    "\n",
    "<p> <strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：[1, 2, 3, 3, 2, 1]\n",
    "<strong> 输出</strong>：[1, 2, 3]\n",
    "</pre>\n",
    "\n",
    "<p> <strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：[1, 1, 1, 1, 2]\n",
    "<strong> 输出</strong>：[1, 2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "<li>链表长度在[0, 20000]范围内。</li>\n",
    "<li>链表元素在[0, 20000]范围内。</li>\n",
    "</ol>\n",
    "\n",
    "<p> <strong>进阶：</strong></p>\n",
    "\n",
    "<p>如果不得使用临时缓冲区，该怎么解决？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-duplicate-node-lcci](https://leetcode.cn/problems/remove-duplicate-node-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-duplicate-node-lcci](https://leetcode.cn/problems/remove-duplicate-node-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:return head\n",
    "        dumy=ListNode(0)\n",
    "        dumy.next=head\n",
    "        arr=[];cur=dumy;after=head\n",
    "        while after:\n",
    "            if after.val not in arr:\n",
    "                arr.append(after.val)\n",
    "                cur=after\n",
    "                after=after.next\n",
    "            else:\n",
    "                cur.next=cur.next.next\n",
    "                after=cur.next\n",
    "        return dumy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        nums = [head.val]\n",
    "        pre, cur = head, head\n",
    "        while cur:\n",
    "            if cur.val not in nums:\n",
    "                nums.append(cur.val)\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "                pre.next = cur\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head or head.next == None:\n",
    "            return head\n",
    "        pre = head\n",
    "        cur = head.next\n",
    "        table = [head.val]\n",
    "        while cur:\n",
    "            if cur.val in table:\n",
    "                pre.next = cur.next\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                table.append(cur.val)\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        result =  []\n",
    "\n",
    "        pre_head = ListNode(0)\n",
    "        pre_head.next = head\n",
    "        s = pre_head\n",
    "        while head:\n",
    "            if head.val in result:\n",
    "                pre_head.next = head.next\n",
    "            else:   \n",
    "                result.append(head.val)\n",
    "                pre_head = pre_head.next    \n",
    "            head = head.next\n",
    "        print(result)\n",
    "        return s.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        occurred = [head.val]\n",
    "        pos = head\n",
    "        while pos.next:\n",
    "            if pos.next.val not in occurred:\n",
    "                occurred.append(pos.next.val)\n",
    "                pos = pos.next\n",
    "            else:\n",
    "                pos.next = pos.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:return head\n",
    "        listA = [head.val]\n",
    "        f,s = head,head.next\n",
    "        while f.next != None:\n",
    "            if s.val not in listA:\n",
    "                listA.append(s.val)\n",
    "                f.next=s\n",
    "                f=s \n",
    "                s=s.next\n",
    "            elif s.next != None:\n",
    "                s=s.next\n",
    "            else:\n",
    "                f.next=None\n",
    "                break\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "\n",
    "        assist = [head.val]\n",
    "        temp = head\n",
    "        while temp.next:\n",
    "            if temp.next.val not in assist:\n",
    "                assist.append(temp.next.val)\n",
    "                temp = temp.next\n",
    "            else:\n",
    "                temp.next = temp.next.next\n",
    "\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "\n",
    "        assist = [head.val]\n",
    "        temp = head\n",
    "        while temp != None and temp.next != None:\n",
    "            if temp.next.val not in assist:\n",
    "                assist.append(temp.next.val)\n",
    "                temp = temp.next\n",
    "            else:\n",
    "                temp.next = temp.next.next if temp.next != None else None\n",
    "\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        vals=[]\n",
    "        pre=None\n",
    "        cur=head\n",
    "        while cur:\n",
    "            if cur.val in vals:\n",
    "                pre.next=cur.next\n",
    "            else:\n",
    "                vals.append(cur.val)\n",
    "                pre=cur\n",
    "\n",
    "            cur=cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "        buffer = [head.val]\n",
    "        cur = head\n",
    "        while cur.next != None:\n",
    "            if cur.next.val not in buffer:\n",
    "                buffer.append(cur.next.val)\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                cur.next = cur.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre = 0 \n",
    "        cur = head\n",
    "        visited = []\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                visited.append(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return head\n",
    "        cur = head\n",
    "        res = [cur.val]\n",
    "        while cur.next != None:\n",
    "            if cur.next.val not in res:\n",
    "                res.append(cur.next.val)\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                cur.next = cur.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "\n",
    "        assist = [head.val]\n",
    "        temp = head\n",
    "        while temp.next != None:\n",
    "            if temp.next.val not in assist:\n",
    "                assist.append(temp.next.val)\n",
    "                temp = temp.next\n",
    "            else:\n",
    "                temp.next = temp.next.next\\\n",
    "\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "        seen = [head.val]\n",
    "        point = head\n",
    "        while point.next != None:\n",
    "            if point.next.val not in seen:\n",
    "                seen.append(point.next.val)\n",
    "                point = point.next\n",
    "            else:\n",
    "                point.next = point.next.next\n",
    "        return head\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        else:\n",
    "            l = []\n",
    "            cur = dummy = ListNode(0, head)\n",
    "            while cur.next is not None:\n",
    "                if cur.next.val not in l:\n",
    "                    l.append(cur.next.val)\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    cur.next = cur.next.next\n",
    "                if cur is None:\n",
    "                    return dummy.next\n",
    "            return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        lst = [head.val]\n",
    "        root = head\n",
    "        while root and root.next:\n",
    "            if root.next.val not in lst:\n",
    "                lst.append(root.next.val)\n",
    "                root = root.next\n",
    "                continue\n",
    "            root.next = root.next.next\n",
    "        return head\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "\n",
    "        assist = [head.val]\n",
    "        temp = head\n",
    "        while temp != None and temp.next != None:\n",
    "            if temp.next.val not in assist:\n",
    "                assist.append(temp.next.val)\n",
    "                temp = temp.next\n",
    "            else:\n",
    "                temp.next = temp.next.next if temp.next != None else None\n",
    "\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        else:\n",
    "            l = []\n",
    "            cur = dummy = ListNode(0, head)\n",
    "            while cur.next is not None:\n",
    "                if cur.next.val not in l:\n",
    "                    l.append(cur.next.val)\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    cur.next = cur.next.next\n",
    "                if cur is None:\n",
    "                    return dummy.next\n",
    "            return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        # 创建空节点f，同时作为慢指针\n",
    "        f = ListNode(0, None)\n",
    "        f.next = head\n",
    "        # 验证唯一列表listA\n",
    "        listA = []\n",
    "        # 快指针s\n",
    "        s = head\n",
    "        while f.next != None:\n",
    "            if s.val not in listA:\n",
    "                listA.append(s.val)\n",
    "                f.next = s\n",
    "                f = s  # 更新f\n",
    "                s = s.next  # 不重复更新s\n",
    "            elif s.next != None:\n",
    "                s = s.next  # 重复更新s\n",
    "            else:\n",
    "                f.next = None\n",
    "                break\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        else:\n",
    "            l = []\n",
    "            cur = dummy = ListNode(0, head)\n",
    "            while cur.next is not None:\n",
    "                if cur.next.val not in l:\n",
    "                    l.append(cur.next.val)\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    cur.next = cur.next.next\n",
    "                if cur is None:\n",
    "                    return dummy.next\n",
    "            return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        exist_vals = []\n",
    "\n",
    "        cur = head\n",
    "        prev = None\n",
    "        \n",
    "        while cur:\n",
    "            if cur.val not in exist_vals:\n",
    "                exist_vals.append(cur.val)\n",
    "                prev = cur\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                prev.next = cur.next\n",
    "                cur = cur.next\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        vals = []\n",
    "        pseudo_head = ListNode(next=head)\n",
    "\n",
    "        cur = pseudo_head\n",
    "        while cur.next: \n",
    "            while cur.next and cur.next.val in vals:\n",
    "                cur.next = cur.next.next\n",
    "            \n",
    "            if cur.next:\n",
    "                vals.append(cur.next.val)\n",
    "                cur = cur.next \n",
    "        \n",
    "        return pseudo_head.next \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        else:\n",
    "            l = []\n",
    "            cur = dummy = ListNode(0, head)\n",
    "            while cur.next is not None:\n",
    "                if cur.next.val not in l:\n",
    "                    l.append(cur.next.val)\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    cur.next = cur.next.next\n",
    "                    if cur is None:\n",
    "                        return dummy.next\n",
    "            return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:return head\n",
    "        dumy=ListNode(0)\n",
    "        dumy.next=head\n",
    "        arr=[];cur=dumy;after=head\n",
    "        while after:\n",
    "            if after.val not in arr:\n",
    "                arr.append(after.val)\n",
    "                cur=after\n",
    "                after=after.next\n",
    "            else:\n",
    "                cur.next=cur.next.next\n",
    "                after=cur.next\n",
    "        return dumy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        lst = [head.val]\n",
    "        root = head.next\n",
    "        pre = head\n",
    "        while root:\n",
    "            if root.val not in lst:\n",
    "                lst.append(root.val)\n",
    "                pre.next = root\n",
    "                pre = pre.next\n",
    "            root = root.next\n",
    "        pre.next = root\n",
    "        return head\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        hash=set()\n",
    "        while cur:\n",
    "            if cur.val in hash:\n",
    "                pre.next=cur.next\n",
    "            else:\n",
    "                hash.add(cur.val)\n",
    "                pre=cur\n",
    "            cur=cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        headNode = head\n",
    "        lst = []\n",
    "        while head.next:\n",
    "            lst.append(head.val)\n",
    "            if head.next.val in lst:\n",
    "                head.next = head.next.next\n",
    "            else:\n",
    "                head = head.next\n",
    "        return headNode\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        visited = set()\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                visited.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        pre, cur = None, head\n",
    "        visited = set()\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                visited.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        rec = []\n",
    "        p1 = head\n",
    "        p2 = head\n",
    "        while p2:\n",
    "            if p2.val not in rec:\n",
    "                rec.append(p2.val)\n",
    "                p1 = p2\n",
    "                p2 = p2.next\n",
    "                \n",
    "            else:\n",
    "                while p2.val in rec:\n",
    "                    p2 = p2.next\n",
    "                    if p2 is None:\n",
    "                        p1.next = None\n",
    "                        break\n",
    "                if p2:\n",
    "                    p1.next = p2\n",
    "                    rec.append(p2.val)\n",
    "                    p1 = p2\n",
    "                    p2 = p2.next                \n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # p1 = head\n",
    "        # p0 = head\n",
    "        # # outhead = ListNode(-1)\n",
    "        # # out = outhead\n",
    "        # rec = []\n",
    "        # # # while p1:\n",
    "        # # #     if p1.val not in rec:\n",
    "        # # #         out.next = ListNode(p1.val)\n",
    "        # # #         out = out.next\n",
    "        # # #         rec.append(p1.val)\n",
    "        # # #     p1 = p1.next\n",
    "        # # # return outhead.next\n",
    "        # while p1:\n",
    "        #     if p1.val not in rec:\n",
    "        #         rec.append(p1.val)\n",
    "        #         p0 = p1\n",
    "        #         p1 = p1.next\n",
    "        #     else:\n",
    "        #         p0.next = p1.next\n",
    "        #         p1 = p1.next\n",
    "        # return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return []\n",
    "        res = []\n",
    "        node = head\n",
    "        while True:\n",
    "            if node.val not in res:\n",
    "                res.append(node.val)\n",
    "            if node.next != None:\n",
    "                node = node.next\n",
    "            else:\n",
    "                break\n",
    "        r = ListNode(res.pop(0))\n",
    "        p = r\n",
    "        while len(res):\n",
    "            p.next = ListNode(res.pop(0))\n",
    "            p = p.next\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return head\n",
    "\n",
    "        occurred = {head.val}\n",
    "        pos = head\n",
    "\n",
    "        while pos.next:\n",
    "            #当前待删除节点\n",
    "            cur = pos.next\n",
    "            if cur.val not in occurred:\n",
    "                occurred.add(cur.val)\n",
    "                pos = pos.next\n",
    "            else:\n",
    "                pos.next = pos.next.next\n",
    "\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        values = set()\n",
    "        while cur:\n",
    "            if cur.val in values:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                values.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        res=ListNode(0)\n",
    "        q=res\n",
    "        p=head\n",
    "        dis={}\n",
    "        while p:\n",
    "            if p.val in dis:\n",
    "                p=p.next\n",
    "            else:\n",
    "                dis[p.val]=1\n",
    "                p=p.next\n",
    "        for i in dis:\n",
    "            res.next=ListNode(i)\n",
    "            res=res.next\n",
    "        return q.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:return \n",
    "        if not head.next:return head\n",
    "        # 进阶方法不存在\n",
    "        # \n",
    "        stack = []\n",
    "        while head:\n",
    "            if head.val not in stack:\n",
    "                stack.append(head.val)\n",
    "            head = head.next\n",
    "        node = ListNode()\n",
    "        l = node\n",
    "        for i in stack:\n",
    "            l.next = ListNode(i)\n",
    "            l = l.next\n",
    "        return node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        visited = set()\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                visited.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        visited = set()\n",
    "        curr = head\n",
    "        prev = None\n",
    "        while curr:\n",
    "            if curr.val in visited:\n",
    "                prev.next = curr.next\n",
    "                curr = curr.next\n",
    "                continue\n",
    "            visited.add(curr.val)\n",
    "            prev = curr\n",
    "            curr = curr.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head: return head\n",
    "        mp = collections.defaultdict(int)\n",
    "        mp[head.val] = 1\n",
    "        pre = head\n",
    "        p = head.next\n",
    "        while p: \n",
    "            if mp[p.val]:\n",
    "                pre.next = p.next\n",
    "                p = p.next\n",
    "            else:\n",
    "                mp[p.val] = 1\n",
    "                p = p.next\n",
    "                pre = pre.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        m = defaultdict(bool)\n",
    "        p = head\n",
    "        while p is not None:\n",
    "            m[p.val] = True\n",
    "            if p.next is not None and m[p.next.val]:\n",
    "                p.next = p.next.next\n",
    "            else:\n",
    "                p = p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        hashmap = {}\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val not in hashmap:\n",
    "                hashmap[cur.val] = True\n",
    "                pre = cur\n",
    "            else:\n",
    "                pre.next = cur.next\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        s = set()\n",
    "        if head:\n",
    "            s.add(head.val)\n",
    "        else:\n",
    "            return head\n",
    "        node = head\n",
    "        while node.next:\n",
    "            if node.next.val in s:\n",
    "                node.next = node.next.next\n",
    "            else:\n",
    "                node = node.next\n",
    "                s.add(node.val)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        l = head\n",
    "        nl = l\n",
    "        if nl != None:\n",
    "            t = nl\n",
    "            s = {nl.val}\n",
    "            while l:\n",
    "                if l.val not in s:\n",
    "                  t.next = l\n",
    "                  t = t.next\n",
    "                  s.add(l.val)\n",
    "                l = l.next\n",
    "            t.next = None\n",
    "        return nl  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        # 创建空节点f，同时作为慢指针\n",
    "        f = ListNode(0, None)\n",
    "        f.next = head\n",
    "        # 验证唯一列表listA\n",
    "        setA = set()\n",
    "        # 快指针s\n",
    "        s = head\n",
    "        while f.next != None:\n",
    "            if s.val not in setA:\n",
    "                setA.add(s.val)\n",
    "                f.next = s\n",
    "                f = s  # 更新f\n",
    "                s = s.next  # 不重复更新s\n",
    "            elif s.next != None:\n",
    "                s = s.next  # 重复更新s\n",
    "            else:\n",
    "                f.next = None\n",
    "                break\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        sets=set()\n",
    "        p=ListNode(0)\n",
    "        p.next=head\n",
    "        pre,cur=p,head\n",
    "        while cur!=None:\n",
    "            if cur.val in sets:\n",
    "                cur=cur.next\n",
    "                continue\n",
    "            sets.add(cur.val)\n",
    "            pre.next=cur\n",
    "            pre,cur=pre.next,cur.next\n",
    "        pre.next=cur\n",
    "        return p.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        s = {head.val}\n",
    "        node = head\n",
    "        while node.next:\n",
    "            if node.next.val in s:\n",
    "                node.next = node.next.next\n",
    "            else:\n",
    "                node = node.next\n",
    "                s.add(node.val)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre = dummy = ListNode(next=head)\n",
    "        cur = head\n",
    "        vis = set()\n",
    "        while cur:\n",
    "            if cur.val in vis:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                vis.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        nums=set()\n",
    "        ans=head\n",
    "        while head:\n",
    "            nums.add(head.val)\n",
    "            while head.next and head.next.val in nums:\n",
    "                head.next=head.next.next\n",
    "            head=head.next\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        visited = set()\n",
    "        pre, cur = None, head\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                visited.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        hashmap={}\n",
    "        if head is None:\n",
    "            return head\n",
    "        pre=None\n",
    "        cur=head\n",
    "        while cur:\n",
    "            if cur.val in hashmap:\n",
    "                pre.next=cur.next\n",
    "            else:\n",
    "                hashmap[cur.val]=1\n",
    "                pre=cur\n",
    "            cur=cur.next\n",
    "        return head\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre,cur=None,head\n",
    "        exist=set()\n",
    "\n",
    "        while cur:\n",
    "            if cur.val not in exist:\n",
    "                exist.add(cur.val)\n",
    "                pre=cur\n",
    "            else:\n",
    "                pre.next=cur.next\n",
    "            \n",
    "            cur=cur.next\n",
    "        return head\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head is None:\n",
    "            return None\n",
    "\n",
    "        hash_set = set()\n",
    "        hash_set.add(head.val)\n",
    "        item = head\n",
    "        while item.next is not None:\n",
    "            # print(item.val)\n",
    "            if item.next.val not in hash_set:\n",
    "                hash_set.add(item.next.val)\n",
    "                item = item.next\n",
    "            else:\n",
    "                item.next = item.next.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        di = defaultdict(int)\n",
    "        p  = head\n",
    "        di[head.val] = 1\n",
    "        while p.next:\n",
    "            p2 = p.next\n",
    "            if di[p2.val] == 0:\n",
    "                di[p2.val] += 1\n",
    "                p = p.next\n",
    "            else:\n",
    "                p.next = p2.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        vHead = ListNode(0)\n",
    "        vHead.next = head\n",
    "        hashtable = set()\n",
    "        pre = vHead\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.val in hashtable:\n",
    "                pre.next = cur.next\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                hashtable.add(cur.val)\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "        return vHead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre,cur = None,head\n",
    "        visited  = set()\n",
    "\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else :\n",
    "                visited.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head==None:\n",
    "            return head\n",
    "        cur=head\n",
    "        vals={cur.val}\n",
    "        while cur and cur.next:\n",
    "            if cur.next.val in vals:\n",
    "                cur.next=cur.next.next\n",
    "            else:\n",
    "                vals.add(cur.next.val)\n",
    "                cur=cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        list1 = []\n",
    "\n",
    "        while cur:\n",
    "            if cur.val not in set(list1):\n",
    "                list1.append(cur.val)\n",
    "                pre = cur\n",
    "            else:\n",
    "                pre.next = cur.next\n",
    "            cur = cur.next\n",
    "        return head\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre = None\n",
    "        cur = head\n",
    "        visited = set()\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                visited.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "# class Solution:\n",
    "#     def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "#         if not head:\n",
    "#             return head\n",
    "#         visited=set()\n",
    "#         pre=None\n",
    "#         cur=head\n",
    "#         while cur:\n",
    "#             if cur.val in visited:\n",
    "#                 pre.next=cur.next\n",
    "#             else:\n",
    "#                 visited.add(cur.val)\n",
    "#                 pre=cur\n",
    "#             cur=cur.next\n",
    "#         return head\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        res={head.val}\n",
    "        cur=head\n",
    "        while cur and cur.next:\n",
    "            if cur.next.val not in res:\n",
    "                res.add(cur.next.val)\n",
    "                cur=cur.next\n",
    "            else:\n",
    "                cur.next=cur.next.next\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        visited = set()\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                visited.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        visited = set()\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                visited.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        ptr1, ptr2 = ListNode(-1), head\n",
    "        ptr1.next = head\n",
    "        val = set()\n",
    "        while ptr2:\n",
    "            if ptr2.val in val:\n",
    "                ptr1.next = ptr2.next\n",
    "                ptr2 = ptr1.next\n",
    "            else:\n",
    "                val.add(ptr2.val)\n",
    "                ptr1 = ptr1.next\n",
    "                ptr2 = ptr2.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for singly-linked list.\n",
    "# # class ListNode:\n",
    "# #     def __init__(self, x):\n",
    "# #         self.val = x\n",
    "# #         self.next = None\n",
    "\n",
    "# class Solution:\n",
    "#     def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "#         dummy=ListNode(-1)\n",
    "#         dummy.next=head \n",
    "#         cur=dummy\n",
    "#         vis=set()\n",
    "#         vis.add(cur.val)\n",
    "#         while cur and cur.next:\n",
    "#             if  cur.next.val not in vis:\n",
    "#                 # vis.add(cur.next.val)\n",
    "#                 cur=cur.next\n",
    "#                 vis.add(cur.val)\n",
    "#             else:\n",
    "#                 # while cur and cur.next and cur.next.val in vis:\n",
    "#                 while cur.next and cur.next.val in vis:\n",
    "#                     cur.next=cur.next.next\n",
    "#                     # cur=cur.next ###只能调针，不能移针\n",
    "#                 if cur.next:\n",
    "#                     cur=cur.next\n",
    "#                     vis.add(cur.val)\n",
    "#         return dummy.next\n",
    "\n",
    "### 官解：哈希\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        occurred = {head.val}\n",
    "        pos = head\n",
    "        # 枚举前驱节点\n",
    "        while pos.next:\n",
    "            # 当前待删除节点\n",
    "            cur = pos.next\n",
    "            if cur.val not in occurred:\n",
    "                occurred.add(cur.val)\n",
    "                pos = pos.next\n",
    "            else:\n",
    "                pos.next = pos.next.next\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        occur = {head.val}\n",
    "        pos = head\n",
    "\n",
    "        while pos.next:\n",
    "            cur = pos.next\n",
    "            if cur.val not in occur:\n",
    "                occur.add(cur.val)\n",
    "                pos = pos.next\n",
    "            else:\n",
    "                pos.next = pos.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        if not head:\n",
    "            return \n",
    "        \n",
    "        s={head.val}\n",
    "\n",
    "        cur=head \n",
    "\n",
    "        while cur.next:\n",
    "            if cur.next.val not in s:\n",
    "                s.add(cur.next.val)\n",
    "                cur=cur.next\n",
    "            else:\n",
    "                cur.next=cur.next.next \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "\n",
    "        assist = {head.val}\n",
    "        temp = head\n",
    "        while temp.next:\n",
    "            if temp.next.val not in assist:\n",
    "                assist.add(temp.next.val)\n",
    "                temp = temp.next\n",
    "            else:\n",
    "                temp.next = temp.next.next\n",
    "\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        hair = head\n",
    "        record = {head.val}\n",
    "        pre, cur = head, head.next\n",
    "        while cur:\n",
    "            if cur.val not in record:\n",
    "                record.add(cur.val)\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                cur = cur.next\n",
    "                pre.next = cur\n",
    "        \n",
    "        return hair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "\n",
    "        if not head:\n",
    "            return \n",
    "        \n",
    "        s=set([head.val])\n",
    "\n",
    "        cur=head \n",
    "\n",
    "        while cur.next:\n",
    "            if cur.next.val not in s:\n",
    "                s.add(cur.next.val)\n",
    "                cur=cur.next\n",
    "            else:\n",
    "                cur.next=cur.next.next \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        hash=set()\n",
    "        while cur:\n",
    "            if cur.val in hash:\n",
    "                pre.next=cur.next\n",
    "            else:\n",
    "                hash.add(cur.val)\n",
    "                pre=cur\n",
    "            cur=cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        pre, cur = None, head\n",
    "        visited = set()\n",
    "        while cur:\n",
    "            if cur.val in visited:\n",
    "                pre.next = cur.next\n",
    "            else:\n",
    "                visited.add(cur.val)\n",
    "                pre = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        prev, curr = None, head\n",
    "        visit = set()\n",
    "        while curr:\n",
    "            if curr.val not in visit:\n",
    "                visit.add(curr.val)\n",
    "                prev, curr = curr, curr.next\n",
    "            else:\n",
    "                prev.next = curr = curr.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        store = set([head.val])\n",
    "        current = head\n",
    "\n",
    "        while current and current.next:\n",
    "            if current.next.val in store:\n",
    "                current.next = current.next.next\n",
    "            else:\n",
    "                store.add(current.next.val)\n",
    "                current = current.next\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        recorder = {head.val}\n",
    "        res = head\n",
    "\n",
    "        while head.next:\n",
    "            if head.next.val not in recorder:\n",
    "                recorder.add(head.next.val)\n",
    "                head = head.next\n",
    "            else:\n",
    "                head.next = head.next.next\n",
    "            \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        ptr1, ptr2 = ListNode(-1), head\n",
    "        ptr1.next = head\n",
    "        val = set()\n",
    "        while ptr2:\n",
    "            if ptr2.val in val:\n",
    "                ptr1.next = ptr2.next\n",
    "                ptr2 = ptr1.next\n",
    "            else:\n",
    "                val.add(ptr2.val)\n",
    "                ptr1 = ptr1.next\n",
    "                ptr2 = ptr2.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        occurred = {head.val}\n",
    "        pos = head\n",
    "        # 枚举前驱节点\n",
    "        while pos.next:\n",
    "            # 当前待删除节点\n",
    "            cur = pos.next\n",
    "            if cur.val not in occurred:\n",
    "                occurred.add(cur.val)\n",
    "                pos = pos.next\n",
    "            else:\n",
    "                pos.next = pos.next.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        rec = set()\n",
    "        node = head\n",
    "        dummy = ListNode(-1)\n",
    "        prev = dummy\n",
    "        while node:\n",
    "            if node.val not in rec:\n",
    "                rec.add(node.val)\n",
    "                prev.next = node\n",
    "                prev = node\n",
    "                node = node.next\n",
    "            else:\n",
    "                prev.next = node.next\n",
    "                node = node.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        recorder = {head.val}\n",
    "        res = head\n",
    "\n",
    "        while head.next:\n",
    "            if head.next.val not in recorder:\n",
    "                recorder.add(head.next.val)\n",
    "                head = head.next\n",
    "            else:\n",
    "                head.next = head.next.next\n",
    "            \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if head == None:\n",
    "            return head\n",
    "\n",
    "        assist = {head.val}\n",
    "        temp = head\n",
    "        while temp.next:\n",
    "            if temp.next.val not in assist:\n",
    "                assist.add(temp.next.val)\n",
    "                temp = temp.next\n",
    "            else:\n",
    "                temp.next = temp.next.next\n",
    "\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeDuplicateNodes(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        hashset={head.val}\n",
    "        pre=head\n",
    "        while pre.next:\n",
    "            cur=pre.next\n",
    "            if cur.val not in hashset:\n",
    "                hashset.add(cur.val)\n",
    "                pre=pre.next\n",
    "            else:\n",
    "                pre.next=pre.next.next\n",
    "        return head\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
